Public key infrastructure refers to an architecture based on asymmetric cryptography that permits computers to authenticate each other and engage in secure messaging. In asymmetric cryptography, a user has a pair of cryptographic keys, known as the public and private keys. The public key is shared and made available to others, while the private key is held secret. The keys are mathematically related to one another such that one key can be used to encrypt information and the other can be used to decrypt it. A well-known characteristic of asymmetric keys is that it is computationally impractical to derive the private key from knowledge of the public key. Information encrypted by one key can only be decrypted by its pair.
Asymmetric cryptography can be used to protect the confidentiality of information through public key encryption. It can also be used to authenticate the information source and attest to the integrity of the data through digital signatures. For instance, two users, A and B, can exchange information in a secure fashion. If user A wants to send information to user B, user A signs the information with its own private key and then encrypts it with user B's public key. Upon receipt of the message, user B decrypts the message using its private key and then validates the message signature with user A's public key. The information sent is kept confidential because it can only be decrypted by the private key that is singularly held by user B. Its integrity can be ascertained by using user A's public key to validate the signature. This is an example of an authenticate first and encrypt second model. It is also possible to encrypt first and authenticate second.
The above method requires user A to have knowledge of user B's public key and user B to have knowledge of user A's public key. In addition, user A needs to validate that the public key purported to be that of user B is indeed true, and vice versa. PKI provides architecture to satisfy this need. PKI binds public keys to entities, enables other entities to verify the public key bindings, and performs the services needed to manage the keys. In particular, PKI defines a system known as a certificate authority (“CA”). The certificate authority is a trusted third party that issues a digital certificate confirming that an entity holds a valid public-private key pair. The certificate authority also uses public key cryptography to sign each digital certificate so that a signed message recipient can establish a chain of trust from the sender to the trusted CA. In the case of validating a sender's signature, the recipient would first verify that the public key contained in the attached certificate is registered with the CA by means of validating the CA's signature of the certificate. The recipient would then use the public key to validate the signature and prove that the sender indeed holds the private key.
PKI has been considered as the digital certificate management system for vehicle communication networks. For example, PKI has been adopted for a new vehicle communication system known as the Vehicle Infrastructure Integration (VII) system. The VII system allows vehicles to communicate with one another and with intelligent roadside equipment, such as traffic signals, using short-range radio technologies such as the Dedicated Short Range Communications (DSRC) or other radio technologies. A goal of the VII system is to improve public safety on the nation's highways by providing the ability for highway controls to communicate with vehicles, such as to electronically report road conditions, and for vehicles to communicate with one another in support of advanced safety applications. One such application is collision avoidance where vehicles would monitor the position of other vehicles on the road and exchange communication with each other about their location and state. When there is the potential for collision, each vehicle would alert its occupant to the danger and potentially take preventive actions, such as braking the vehicle.
FIG. 1 illustrates components of a vehicle communication system such as the VII system. An IP-based VII backbone network (100) interconnects a multitude of radio equipped roadside equipment (RSE) (130) and application servers (110, 120). Each RSE (130) communicates (190) with vehicles (160, 170) within its radio zone (140) to deliver messages between the vehicles and the network devices and applications connected to the backbone network. Vehicles (160, 170) within an RSE zone (140) communicate (150) directly with one another. In addition, vehicles (170) within an RSE zone (140) may communicate (195) with vehicles (180) that are outside the RSE zone. More generally, vehicles need not be within any RSE coverage to communicate with one another.
A fundamental concern in vehicle communication networks such as in the VII system is the privacy of vehicle occupants and owners. Privacy become a concern when vehicles are mandated to participate in certain communications applications, such as providing probe data to a government run data center as currently envisioned in the VII system. Vehicle privacy is compromised of two elements: Anonymity and Unlinkability. Anonymity is the inability to identify or enable identification of a vehicle, its owner, or occupants because of its participation in a vehicle communication system. This includes, but is not limited to, message communications and information processed or retained within vehicle communication system. Identifying a vehicle means obtaining one or more distinguishable vehicle attributes that can be definitively linked to the vehicle, its owner and/or vehicle occupant. Unlinkability is the inability to definitively associate observations, data, or information, such as anonymous messages, with a particular, but possibly unidentified, vehicle, vehicle owner, or occupant as a result of participating in vehicle communication system. Unlinkability implies the inability to track a vehicle's path, especially as it moves from one radio zone to another.
To protect privacy of the vehicles and its occupants, vehicle messages need to be anonymous, i.e., they cannot be associated with any individual vehicle. However, to maintain the integrity of the system and to make sure that safety applications are not impacted by malicious communication, vehicle messages must be authenticated. Many vehicle communications, such as the VII system impose the dual requirement of anonymous, but authenticated communication. Others have proposed a method based on public key cryptography that provides for anonymity and message authentication. In this method, each vehicle is assigned n key pairs (and their associated certificates) from a system-wide pool of N key pairs by a certificate authority. The key pairs may be assigned such that there is an even distribution of keys among the vehicles. Since the number of vehicles in the system is much greater than N, there is substantial reuse of key pairs, i.e., more than one vehicle uses the same key. Using this method, any one of a number of vehicles might be able to generate and sign or encrypt a message with a particular key, hence providing a level of privacy to each individual vehicle. However, each message can be authenticated by verifying the registration of the key with the CA and validating the message signature.
It is a goal of the VII system to maintain vehicle anonymity throughout the entire system following a “privacy by design” approach. In particular, the certificate authority is an entity that has the potential to contain much information about the keys that are assigned to vehicles. Several abuses of the certificate authority could compromise vehicle privacy and negatively impact commercial entities that participate in the VII system. For instance, it might be possible for the certificate authority to assign one or more unique keys to a vehicle so that it can be unequivocally identified whenever it communicates. Other than the vehicle, the certificate authority is the only other entity that has knowledge of the keys and certificates that were assigned to each vehicle. Using parameters such as n=5 and N=10,000, the probability that a vehicle has any particular set of n evenly distributed keys is extremely small and is given by the inverse of the number of combinations of 5 keys taken from 10,000 (i.e., “10,000 choose 5”) or approximately 1.2e-18. The set of n keys therefore provides a unique identifier for each vehicle and could potentially be used to track a vehicle. In addition, insider threats within the VII system operator and the potential for outside forces to influence a system operator to take advantage of the certificate authority to violate vehicle privacy may exist.
The foregoing discussion highlights the need for a method and system to construct a certificate authority that minimizes the potential for any one party associated with the certificate authority to abuse its position to violate vehicle privacy. In particular, a certificate management system and method is sought that will not provide any element of the certificate management infrastructure with the ability to link individual certificates, which contain no identifying information, with certificate holders.
In another aspect, the present disclosure addresses a large scale network with certified communications, where each node has a limited number of certificates, and where the use of a certain certificate may inadvertently identify which node sent the message. This is, for instance, the case when the pool of available certificates is large, and the number of nodes communicating is small, and the nodes randomly or indiscriminately select from among their available certificates to send messages. In contrast, it is often not desirable to first explicitly communicate available keys in the community of interest. While known distributed consensus algorithms may be able to achieve the goal of communication with non-unique keys, those algorithms require additional communication overhead. Therefore, typically a large communication overhead is involved. Different areas of application may not allow for any communication overhead related to key selection at all. Furthermore, key selection protocols based on explicit mutual communication may not be desirable in many areas of application. Thus, what is desirable is to have individual nodes select a certificate (also referred to as a “key”), which is used by more than one node, so that each node using that key cannot be identified by use of the key alone. It is further desirable to do so without additional communication overhead for key selection.